This disclosure relates generally to data decoding, and mere particularly to detecting and correcting near-codewords in iterative decoders for data encoded with a low-density parity check (LDPC) encoder.
An LDPC code is an error correcting code that may be used in the transmission of information through a noisy communications channel, with or without memory. A variety of LDPC decoding techniques may be used to recover and correct the information received from The channel, most of which are iterative in nature.
In the case of a memoryless channel, an LDPC decoder may directly receive log-likelihood-ratio (LLR) information, a bit reliability metric representative of the encoded data received from the channel, for use in the decoding operation. In the case of a channel with memory, a soft-in soft-out (SISO) channel detector, such as a soft output Viterbi algorithm (SOVA) detector, may be used in conjunction with the LDPC decoder. The decoding operation may alternate between use of the SISO channel detector and the LDPC decoder in order to decode the data. In particular, LLR information may be passed from the SISO channel detector to the LDPC decoder for use in the next LDPC decoding iteration and vice versa, in an iterative process that may be repeated, as desired, in order to improve data reliability.
LDPC codes may be represented by many different types of parity check matrices. The structure of an LDPC code's parity check matrix may be, for example, random, cyclic, or quasi-cyclic. LDPC codes defined by quasi-cyclic parity check matrices are particularly common and computationally efficient. These codes are known as quasi-cyclic low density parity check (QC-LDPC) codes.
A parity check matrix representative of a particular LDPC code may correspond to a bi-partite graph with check nodes and variable nodes. An LDPC decoder may decode received codewords using an iterative message passing algorithm, in which each iteration or sub-iteration includes two update steps involving the variable nodes and check nodes. (As used herein, the term “message” refers to a numerical value, usually representing an LLR.) In the first update step, messages may be passed from some (or all) check nodes to some (or all) variable nodes, and in the second update step, messages may be passed from some (or all) variable nodes to some (or all) check nodes.
An LDPC decoder may perform the update steps in accordance with a serial (layered) or flooding decoding schedule. In the flooding technique, all check nodes may be updated before a variable node may be updated and all variable nodes may be updated before a check node may be updated. In layered decoding, on the other hand, only those variable nodes necessary for updating a particular check node may be updated; or only those check nodes necessary for updating a particular variable node may be updated. An LDPC decoder that uses a layered update schedule for the message passing algorithm is herein referred to as a layered LDPC decoder.
Many iterative decoders currently iterate up to some predetermined number of iterations or until a correct codeword is detected. This, however, can be inefficient. For example, in some situations, near-codewords may arise that may never converge to a correct codeword even with significantly more iterations than the predetermined number of iterations.
Therefore, it would be desirable to provide LDPC decoders that can detect and correct near-codewords before the decoder iterates up to the predetermined number of iterations. Detecting and correcting the near-codewords may improve system performance and reduce the number of errors.
The background description provided herein is for the purpose of generally presenting the context of the disclosure. Work of the inventors hereof, to the extent the work is described in this background section, as well as aspects of the description that may not otherwise qualify as prior art at the time of filing, are neither expressly nor impliedly admitted as prior art against the present disclosure.